/*!
\file AlgKruskal.cpp
\brief Contains implementation of AlgKruskal.
\ingroup Plugins
*/

#include"AlgKruskal.h" 

AlgKruskal::AlgKruskal( Graph *g ): Algorithm( g ){
	containerAdd();
}

AlgKruskal::~AlgKruskal(){
	
}

void AlgKruskal::run(){
	sortEdges();
	populateNodes();
	Container &edges = container(0);
	
	while( edges.size() > 0 ){
		int src = containerContaining(edges[0]->edge()->from());
		int dst = containerContaining(edges[0]->edge()->to());
		if( src != -1 && dst != -1 && src != dst ){
			merge(src, dst, *edges[0]->edge());
		}
		delete edges.takeAt(0);
	}
	
	for( int i = graph()->numEdges() - 1; i >= 0; i-- ){
		const Edge &e = graph()->edge(i);
		bool found = false;
		for( int j = 0; j < container(1).size() && !found; j++ ){
			found = container(1)[j]->edge() != 0 && *container(1)[j]->edge() == e;
		}
		if( !found )
			graph()->removeEdge(e);
	}
}

void AlgKruskal::sortEdges(){
	Container &edges = container(0);
	QList<Edge> E;
	QList<int> C;
	
	for( int i = 0; i < graph()->numEdges(); i++ ){
		const Edge &e = graph()->edge(i);
		E.push_back(Edge(e));
		C.push_back(e.label().toInt());
	}
	
	while( E.size()>0 ){
		int min = C[0];
		int imin = 0;
		for( int i = 1; i < C.size(); i++ ){
			if( C[i] < min ){
				min = C[i];
				imin = i;
			}
		}
		
		edges.push_back( (new ContainerElement)->setEdge(E[imin]) );
		E.removeAt(imin);
		C.removeAt(imin);
	}
}

void AlgKruskal::populateNodes(){
	for( int i = 0; i < graph()->numNodes(); i++ ){
		containerAdd();
		container( containerCount() - 1 ).push_back( (new ContainerElement)->setNode(graph()->node(i)) );
	}
}

int AlgKruskal::containerContaining( const Node &n ){
	for( int i = 1; i < containerCount(); i++ ){
		for( int j = 0; j < container(i).size(); j++ ){
			if( *container(i)[j]->node() == n )
				return i;
		}
	}
	return -1;
}

void AlgKruskal::swap( int &a, int &b ){
	int c = a;
	a = b;
	b = c;
}

void AlgKruskal::merge( int src, int dst, const Edge &e ){
	if( src < dst )
		swap(src, dst);
	while( container(src).size() > 0 ){
		container(dst).push_back( container(src).takeAt(0) );
	}
	for( int i = 0; i < container(dst).size(); i++ ){
		if( container(dst)[i]->edge() == 0 ){
			container(dst)[i]->setEdge(e);
			break;
		}
	}
	
	while(true){
		if( container( containerCount()-1 ).size() == 0 )
			containerPop();
		else
			break;
	}
}
